package com.aqie.easy.linkedlist;

import com.aqie.easy.structure.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * 160 相交链表 todo
 */
public class GetIntersectionNode {
    /**
     * 1,暴力法, 注意链表循环后 指针位置
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tmp = headB;
        while (headA != null){
            while (headB != null){
                if (headA == headB) return headB;
                headB = headB.next;
            }
            headA = headA.next;
            headB = tmp;
        }
        return null;
    }

    /**
     * 2, 哈希表
     * 时间复杂度 O(m+n)
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        // 遍历链表存入 Set
        while (headA != null){
            set.add(headA);
            headA = headA.next;
        }
        while (headB != null){
            if (set.contains(headB)){
                return headB;
            }else {
                headB = headB.next;
            }
        }
        return null;
    }

    /**
     * 3. 双指针
     * 时间复杂度 O(m+n)
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;

    }
}
